import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode:剑指 Offer 60. n个骰子的点数
 * <a href="https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/description/">...</a>
 * User: DELL
 * Date: 2023-09-11
 * Time: 23:07
 */
public class Solution {
    /**
     * 解题思路: (动态规划)
     * 首先对于本题来说,使用暴力法列举是不可行的,因此只能另寻他路.
     * 而对于本题来说有一个很巧妙的点就是,若已知 n-1 个筛子的概率分布
     * 数组 f(n-1),那么可以较为简单的求出 n 个筛子的概率分布 f(n).
     * 即 f(n,x) = (f(n-1,x-1) + f(n-1,x-2) + ... + f(n1,x-6))/6
     * 那么对于以上关系,我们可以反向来考虑,即 f(n-1,x)对f(n,x+1),
     * f(n,x+2) ... f(n,x+6)均贡献了自己概率的六分之一,那么我们就可以
     * 利用这个关系来进行动态规划.
     * <p>
     * 若上述题解不是很懂,可以参考如下 leetcode 官方题解
     * <a href="https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/solutions/637778/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/">...</a>
     *
     * @param n
     * @return
     */
    public double[] dicesProbability(int n) {
        double[] res = new double[6];
        Arrays.fill(res, 1.0 / 6);
        for (int i = 2; i <= n; i++) {
            double[] temp = new double[5 * i + 1];
            for (int j = 0; j < res.length; j++) {
                for (int k = 0; k < 6; k++) {
                    temp[j + k] += res[j] / 6.0;
                }
            }
            res = temp;
        }
        return res;
    }
}